// 最好情况：O(nlogn), 最坏情况
export default function heapSort(arr: number[]): number[] {
  const n = arr.length;

  // 原地建堆
  const start = Math.floor(n / 2 - 1);
  for (let i = start; i >= 0; i--) {
    heapDown(arr, n, i);
  }

  function heapDown(arr: number[], n: number, index: number) {
    while (2 * index + 1 < n) {
      const leftIndex = 2 * index + 1;
      const rightIndex = 2 * index + 2;
      let largetIndex = leftIndex;
      if (rightIndex < n && arr[rightIndex] > arr[leftIndex]) {
        largetIndex = rightIndex;
      }

      if (arr[index] > arr[largetIndex]) {
        break;
      }

      [arr[index], arr[largetIndex]] = [arr[largetIndex], arr[index]];
      index = largetIndex;
    }
  }

  // 排序
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapDown(arr, i - 1, 0);
  }

  return arr;
}

console.log(heapSort([12, 232, 43, 12, 423, 1, 2, 3]));
